﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace NonBinaryTree
{
    public class NonBinaryTree<T>
        where T : NonBinaryTreeNode<T>
    {
        public NonBinaryTree()
        {
            RootNode = null;
        }

        public NonBinaryTree(T root)
        {
            RootNode = root;
        }

        public T RootNode { get; set; }

        public virtual string GetTree()
        {
            if (RootNode != null)
            {
                StringBuilder treeNodes = new StringBuilder();
                GetTreeHelper(RootNode, ref treeNodes, 0);
                return treeNodes.ToString();
            }
            else
            {
                throw new NullReferenceException();
            }
        }

        public virtual T FindNode(Predicate<NonBinaryTreeNode<T>> predicate)
        {
            T node = default(T);
            FindNodeHelper(predicate, RootNode, ref node);
            return node;
        }

        public virtual NonBinaryTreeNodeList<T> FindAllNodes(Predicate<NonBinaryTreeNode<T>> predicate)
        {
            NonBinaryTreeNodeList<T> nodes = new NonBinaryTreeNodeList<T>();
            FindAllNodesHelper(predicate, RootNode, ref nodes);
            return nodes;
        }

        private void GetTreeHelper(T root, ref StringBuilder nodes, int level)
        {
            nodes.AppendFormat("{0}{1} \r\n", String.Empty.PadLeft(level * 5), root.Name);

            ++level;
            foreach (T newNode in root.Children)
            {
                GetTreeHelper(newNode, ref nodes, level);
            }
        }

        private void FindNodeHelper(Predicate<NonBinaryTreeNode<T>> predicate, T root, ref T node)
        {
            T temp = (T)root.Children.Find(predicate);
            if (temp != null)
            {
                node = temp;
                return;
            }

            foreach (T newNode in root.Children)
            {
                FindNodeHelper(predicate, newNode, ref node);
            }
        }

        private void FindAllNodesHelper(Predicate<NonBinaryTreeNode<T>> predicate, T root, ref NonBinaryTreeNodeList<T> nodes)
        {
            T temp = (T)root.Children.Find(predicate);
            if (temp != null)
            {
                nodes.Add(temp, false);
            }

            foreach (T newNode in root.Children)
            {
                FindAllNodesHelper(predicate, newNode, ref nodes);
            }
        }
    }
}
